package com.sx.sx1.lintcode.day717;

public class LC31 {

    static class Solution {

        public int partitionArray(int[] nums, int k) {
            //空间复杂度，要设置一个offset值，将<k的值与offset位置上的值交换位置，然后offset++
            int n  = nums.length;
            int offset =0;
            for (int i = 0; i <n ; i++) {
                if(nums[i] <k){
                    int t = nums[i];
                    nums[i] = nums[offset];
                    nums[offset]=t;
                    offset++;
                }
            }
            return offset;
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
31 · 数组划分
算法
中等
通过率
37%

题目
题解92
笔记
讨论99+
排名
记录
描述
给出一个整数数组 nums 和一个整数 k。划分数组（即移动数组 nums 中的元素），使得：

所有小于k的元素移到左边
所有大于等于k的元素移到右边
返回数组划分的位置，即数组中第一个位置 i，满足 nums[i] 大于等于 k。

如果数组所有数都小于 k ，则应该返回 nums.length
0 <= nums.length <= 20000<=nums.length<=2000

样例
样例 1：

输入：

nums = []
k = 9
输出：

0
解释：

空数组，输出0

样例 2：

输入：

nums = [3,2,2,1]
k = 2
输出：

1
解释：

真实的数组为[1,2,2,3].所以返回 1

挑战
使用 O(n)O(n) 的时间复杂度在数组上进行划分。

标签
相关题目

761
最小子集
中等

373
奇偶分割数组
简单

96
链表划分
简单

625
数组划分II
中等

144
交错正负数
中等
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
30 分 00 秒
12345678910
public class Solution {
    /**
     * @param nums: The integer array you should partition
     * @param k: An integer
     * @return: The index after partition

public int partitionArray(int[] nums, int k) {
    // write your code here
}
}
控制台
        历史提交

 */
